home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / FROMUTS / UNIXLIB37B / src / c / alloc_ < prev    next >
Text File  |  1992-12-30  |  8KB  |  460 lines
  1. #ifdef __STDC__
  2. static char sccs_id[] = "@(#) alloc.c 4.0 "__DATE__" HJR";
  3. #else
  4. static char sccs_id[] = "@(#) alloc.c 4.0 15/9/90 HJR";
  5. #endif
  6.  
  7. /* alloc.c (c) Copyright 1990 H.Rogers */
  8.  
  9. /* features multiple free lists hashed on block size */
  10.  
  11. #ifdef __STDC__
  12. #include <stddef.h>
  13. #include <stdlib.h>
  14. extern void *sbrk(int);
  15. #else
  16. #include "sys/types.h"
  17. void *malloc();
  18. void *realloc();
  19. void free();
  20. extern void *sbrk();
  21. #endif
  22. #include <string.h>
  23.  
  24. #ifdef M_DEBUG
  25. #include <stdio.h>
  26. #include <signal.h>
  27. #ifdef __STDC__
  28. static int __m_fail(char *exp,char *file,int line)
  29. #else
  30. extern int kill();
  31. extern int getpid();
  32. #define raise(x) kill(getpid(),x)
  33. static int __m_fail(exp,file,line)
  34. char *exp,*file;
  35. int line;
  36. #ifndef SIGABRT
  37. #define SIGABRT SIGQUIT
  38. #endif
  39. #endif
  40. {
  41. fprintf(stderr,"\n\"%s\", line %d: Assertion failed: %s\n",file,line,exp);
  42. raise(SIGABRT);
  43. return(0);
  44. }
  45. #ifdef __STDC__
  46. #define assert(x)    (void)((x) ? 0 : __m_fail(#x,__FILE__,__LINE__))
  47. #else
  48. #ifndef __FILE__
  49. #define __FILE__ "alloc.c"
  50. #endif
  51. #ifndef __LINE__
  52. #define __LINE__ 0
  53. #endif
  54. #define assert(x)    (void)((x) ? 0 : __m_fail("x",__FILE__,__LINE__))
  55. #endif
  56. #ifdef ARCH
  57. #include "sys/syslib.h"
  58. #define addr(x)     ((void *)(x) >= __base && (void *)(x) < __break)
  59. #else
  60. #define addr(x)     ((x) ? ((*x) | 1) : 0)    /* force SIGSEGV if bad */
  61. #endif
  62. #define MAGIC        0x4349474d
  63. #endif
  64.  
  65. typedef struct _blk
  66.   {
  67. #ifdef M_DEBUG
  68.   int        magic;
  69.   struct _blk    *range;
  70. #endif
  71.   struct _blk    *next;
  72.   size_t    size;
  73.   } blk;
  74.  
  75. #ifdef M_DEBUG
  76. #define BLKSIZ        16    /* smallest power of 2 >= sizeof(blk) */
  77. #else
  78. #define BLKSIZ        8
  79. #endif
  80.  
  81. #define blkalign(x)    (((x) + (BLKSIZ<<1) - 1) & (~(BLKSIZ - 1)))
  82.  
  83. #define NFL    8
  84.  
  85. static blk __fl[NFL];
  86. static size_t __flmin[NFL] =
  87.   {
  88.   4096    + BLKSIZ,
  89.   1024    + BLKSIZ,
  90.   256    + BLKSIZ,
  91.   64    + BLKSIZ,
  92.   32    + BLKSIZ,
  93.   16    + BLKSIZ,
  94.   8    + BLKSIZ,
  95.   0    + BLKSIZ    /* catchall */
  96.   };
  97.  
  98. #define MEMINC        4096    /* sbrk() memory increment */
  99.  
  100. #ifdef __STDC__
  101. void __allocinit(void)
  102. #else
  103. void __allocinit()
  104. #endif
  105. {
  106. register blk *b;
  107. register int i;
  108.  
  109. #ifdef M_DEBUG
  110. assert(sizeof(struct _blk) >= BLKSIZ);
  111. #endif
  112.  
  113. for (i = 0; i < NFL; i++)
  114.   {
  115.   b = __fl + i;
  116.   b->next = b;
  117.   b->size = BLKSIZ;
  118. #ifdef M_DEBUG
  119.   b->magic = MAGIC;
  120.   b->range = __fl + ((i + 1) % NFL);
  121. #endif
  122.   }
  123. }
  124.  
  125. #ifdef __STDC__
  126. void *malloc(register size_t size)
  127. #else
  128. void *malloc(size)
  129. register size_t size;
  130. #endif
  131. {
  132. register blk *b,*p,*q;
  133. register int i;
  134.  
  135. if (!(size = blkalign(size))) return(0);
  136.  
  137. for (i = 0; size < __flmin[i]; i++);
  138. q = 0;
  139. p = __fl + i;
  140. b = p->next;
  141.  
  142. #ifdef M_DEBUG
  143. assert(addr(p));
  144. assert(p->magic == MAGIC);
  145. assert(addr(p->range));
  146. assert(p->range->magic == MAGIC);
  147. #endif
  148.  
  149. while (b > p)
  150.   {
  151. #ifdef M_DEBUG
  152.   assert(addr(b));
  153.   assert(addr(b->next));
  154.   assert(b->magic == MAGIC);
  155.   assert(addr(b->range));
  156.   assert(b->range->magic == MAGIC);
  157. #endif
  158.   if (b->size >= size)
  159.     { p->next = b->next; goto malloc; }
  160.   q = p;
  161.   p = b;
  162.   b = b->next;
  163.   }
  164.  
  165.   {
  166.   register void *m;
  167.   register int _size;
  168. #ifdef M_DEBUG
  169.   register blk *r;
  170. #endif
  171.  
  172.   _size = (size/MEMINC + 1) * MEMINC;
  173.   if ((m = sbrk(_size)) == (void *)-1) return(0);
  174.   if ((char *)p + p->size == (char *)m)
  175.     {
  176. #ifdef M_DEBUG
  177.     assert(q);
  178. #endif
  179.     b = p; p = q; p->next = b->next;
  180.     b->size += _size;
  181.     }
  182.   else
  183.     {
  184.     b = (blk *)m;
  185.     b->size = _size;
  186. #ifdef M_DEBUG
  187.     b->magic = MAGIC;
  188.     for (r = p; r->range > r; r = r->range);
  189.     assert(addr(r));
  190.     assert(addr(r->range));
  191.     b->range = r->range;
  192.     r->range = b;
  193. #endif
  194.     }
  195.  
  196. #ifdef M_DEBUG
  197.   assert(addr(b));
  198. #endif
  199.   }
  200.  
  201. malloc:
  202.  
  203. if (b->size > (size + __flmin[i]))
  204.   {
  205.   register blk *n;
  206.   register int j;
  207.  
  208.   j = b->size - size;
  209.  
  210.   n = (blk *)((char *)b + size);
  211.  
  212.   n->next = p->next;
  213.   p->next = n;
  214.   n->size = j;
  215.   b->size = size;
  216. #ifdef M_DEBUG
  217.   n->magic = MAGIC;
  218.   n->range = b->range;
  219.   b->range = n;
  220. #endif
  221.   }
  222.  
  223. #ifdef M_DEBUG
  224. assert(b->magic == MAGIC);
  225. assert(b->range->magic == MAGIC);
  226. #endif
  227.  
  228. return((void *)((char *)b + BLKSIZ));
  229. }
  230.  
  231. #ifdef __STDC__
  232. void *realloc(register void *_a,register size_t size)
  233. #else
  234. void *realloc(_a,size)
  235. register void *_a;
  236. register size_t size;
  237. #endif
  238. {
  239. register blk *a,*b,*p,*q;
  240. register int i;
  241. int j;
  242.  
  243. if (!(_a)) return(malloc(size));
  244.  
  245. if (!(size = blkalign(size))) { free(_a); return(0); }
  246.  
  247. #ifdef M_DEBUG
  248. assert(addr(_a));
  249. #endif
  250.  
  251. a = (blk *)((char *)_a - BLKSIZ);
  252.  
  253. #ifdef M_DEBUG
  254. assert(addr(a));
  255. assert(a->magic == MAGIC);
  256. assert(addr(a->range));
  257. assert(a->range->magic == MAGIC);
  258. #endif
  259.  
  260. for (i = 0; a->size < __flmin[i]; i++);
  261. q = 0;
  262. p = __fl + i;
  263. b = p->next;
  264.  
  265. #ifdef M_DEBUG
  266. assert(addr(p));
  267. assert(p->magic == MAGIC);
  268. assert(addr(p->range));
  269. assert(p->range->magic == MAGIC);
  270. #endif
  271.  
  272. while (b > p)
  273.   {
  274. #ifdef M_DEBUG
  275.   assert(addr(b));
  276.   assert(addr(b->next));
  277.   assert(b->magic == MAGIC);
  278.   assert(addr(b->range));
  279.   assert(b->range->magic == MAGIC);
  280. #endif
  281.   if (b > a) break;
  282.   q = p;
  283.   p = b;
  284.   b = b->next;
  285.   }
  286.  
  287. while ((char *)a + a->size == (char *)b)
  288.   {
  289.   a->size += b->size;
  290. #ifdef M_DEBUG
  291.   assert(a->range == b);
  292.   a->range = b->range;
  293.   b->magic = 0;
  294. #endif
  295.   b = p->next = b->next;
  296.   }
  297.  
  298. j = a->size - BLKSIZ;
  299.  
  300. if (a->size < size)
  301.   {
  302.   if ((char *)p + p->size == (char *)a && p->size + a->size >= size)
  303.     {
  304. #ifdef M_DEBUG
  305.     assert(q);
  306. #endif
  307.     b = p; p = q;
  308.     b->size += a->size;
  309. #ifdef M_DEBUG
  310.     assert(b->range == a);
  311.     b->range = a->range;
  312.     a->magic = 0;
  313. #endif
  314.     memmove((char *)b + BLKSIZ,_a,j); _a = (char *)(a = b) + BLKSIZ;
  315.     b = p->next = b->next;
  316.     }
  317.   else
  318.     {
  319.     register void *__a;
  320.  
  321.     if (!(__a = malloc(size - BLKSIZ))) return(0);
  322.     memcpy(__a,_a,j);
  323.     free(_a);
  324.     return(__a);
  325.     }
  326.   }
  327.  
  328. if (a->size > (size + __flmin[i]))
  329.   {
  330.   register blk *n;
  331.   register int j;
  332.  
  333.   j = a->size - size;
  334.  
  335.   n = (blk *)((char *)a + size);
  336.  
  337.   n->next = p->next;
  338.   p->next = n;
  339.   n->size = j;
  340.   a->size = size;
  341. #ifdef M_DEBUG
  342.   n->magic = MAGIC;
  343.   n->range = a->range;
  344.   a->range = n;
  345. #endif
  346.   }
  347.  
  348. #ifdef M_DEBUG
  349. assert(a == (blk *)((char *)_a - BLKSIZ));
  350. assert(a->magic == MAGIC);
  351. assert(addr(a->range));
  352. assert(a->range->magic == MAGIC);
  353. #endif
  354.  
  355. return(_a);
  356. }
  357.  
  358. #ifdef __STDC__
  359. void free(register void *_a)
  360. #else
  361. void free(_a)
  362. register void *_a;
  363. #endif
  364. {
  365. register blk *a,*p,*b;
  366. register int i;
  367.  
  368. if (!_a) return;
  369.  
  370. #ifdef M_DEBUG
  371. assert(addr(_a));
  372. #endif
  373.  
  374. a = (blk *)((char *)_a - BLKSIZ);
  375.  
  376. #ifdef M_DEBUG
  377. assert(addr(a));
  378. assert(a->magic == MAGIC);
  379. assert(addr(a->range));
  380. assert(a->range->magic == MAGIC);
  381. #endif
  382.  
  383. for (i = 0; a->size < __flmin[i]; i++);
  384. p = __fl + i;
  385. b = p->next;
  386.  
  387. #ifdef M_DEBUG
  388. assert(addr(p));
  389. assert(p->magic == MAGIC);
  390. assert(addr(p->range));
  391. assert(p->range->magic == MAGIC);
  392. #endif
  393.  
  394. while (b > p)
  395.   {
  396. #ifdef M_DEBUG
  397.   assert(addr(b));
  398.   assert(addr(b->next));
  399.   assert(b->magic == MAGIC);
  400.   assert(addr(b->range));
  401.   assert(b->range->magic == MAGIC);
  402. #endif
  403.   if (b > a) break;
  404.   p = b;
  405.   b = b->next;
  406.   }
  407.  
  408. while ((char *)a + a->size == (char *)b)
  409.   {
  410.   a->size += b->size;
  411. #ifdef M_DEBUG
  412.   assert(a->range == b);
  413.   a->range = b->range;
  414.   b->magic = 0;
  415. #endif
  416.   b = p->next = b->next;
  417.   }
  418. if ((char *)p + p->size == (char *)a)
  419.   {
  420.   p->size += a->size;
  421. #ifdef M_DEBUG
  422.   assert(p->range == a);
  423.   p->range = a->range;
  424.   a->magic = 0;
  425. #endif
  426.   }
  427. else
  428.   {
  429.   a->next = p->next;
  430.   p->next = a;
  431.   }
  432. }
  433.  
  434. #ifdef M_DEBUG
  435. #ifdef __STDC__
  436. void __m_debug(void)    /* dump free lists */
  437. #else
  438. void __m_debug()
  439. #endif
  440. {
  441. register blk *b;
  442. register int i;
  443.  
  444. for (i = 0; i < NFL; i++)
  445.   {
  446.   printf("\nfl: %d ( >= %d )\n",i,__flmin[i] - BLKSIZ);
  447.   b = __fl + i; do
  448.     {
  449.     b = b->next;
  450.     printf("%7x: next: %7x [%7x] size: %x\n",b,b->next,
  451.     (char *)b + b->size,b->size - BLKSIZ);
  452.     assert(addr(b));
  453.     assert(b->magic == MAGIC);
  454.     }
  455.   while (b->next > b);
  456.   }
  457. putchar('\n');
  458. }
  459. #endif
  460.